/*
 * @lc app=leetcode.cn id=21 lang=typescript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：迭代
//  类似归并最后合并的过程

//  复杂度：O(n + m)  O(1)
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let newHead = new ListNode(), p = newHead, p1 = l1, p2 = l2
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }

    if (p1 != null) {
        p.next = p1;
    }

    if (p2 != null) {
        p.next = p2;
    }
    return newHead.next

};
// @lc code=end
import { ListNode } from './type'
let l1 = new ListNode(1, new ListNode(2, new ListNode(4)))
let l2 = new ListNode(1, new ListNode(3, new ListNode(4)))
console.log(ListNode.printList(mergeTwoLists(l1, l2)));

//  递归
//  复杂度：O(n + m)  O(n + m)
function mergeTwoLists2(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
let l3 = new ListNode(1, new ListNode(2, new ListNode(4)))
let l4 = new ListNode(1, new ListNode(3, new ListNode(4)))
console.log(ListNode.printList(mergeTwoLists2(l3, l4)));
